
//给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 8 
// -10 <= nums[i] <= 10 
// 
//
// 
//
// 注意：本题与主站 47 题相同： https://leetcode-cn.com/problems/permutations-ii/ 
// Related Topics 数组 回溯 
// 👍 1 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
  * 题目Id：剑指 Offer II 084
  * 题目：含有重复元素集合的全排列 
  * 日期：2021-08-23 15:51:06
*/
public class SevenP8L0Z {
    public static void main(String[] args) {
        Solution solution = new SevenP8L0Z().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

        List<List<Integer>> lists= new LinkedList<>();
        public void dfs( int [] nums, LinkedList<Integer> list, int[] visited){
            if (list.size()==nums.length){
                lists.add(new ArrayList<>(list));
                return;
            }
            for (int i=0;i<nums.length;i++){
                if (visited[i]!=1){
                    list.add(nums[i]);
                    visited[i]=1;
                    dfs(nums,list,visited);
                    //回溯的精髓 恢复状态 退后一步
                    visited[i]=0;
                    list.removeLast();
                }
            }
        }
    public List<List<Integer>> permuteUnique(int[] nums) {
        dfs(nums,new LinkedList<>(),new int [nums.length]);
        return lists;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}    
